from typing import List


"""
7,8,0, 1,2,3,4,5,6
中间是2
如果左边 >= 中间 and 中间 < 右边，转折点在左边

2,3,4,5,6,7,8, 0,1

中间是6
如果左边<= 中间 and  中间 >= 右边  ,转折点在右边

test8()的时候错误了，因为不能丢弃任意一边
"""


class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        def half(left, right):
            print(left, right)
            mid = (left + right) // 2

            if nums[mid] == target:
                return True
            if left >= right:
                return False
            if nums[left] > nums[mid] and nums[mid] < nums[right]:
                # 转折点在左边

                if nums[mid] <= target <= nums[right]:
                    print("x1")
                    return half(mid + 1, right)
                else:
                    print("x2")
                    return half(left, mid - 1)
            elif nums[left] < nums[mid] > nums[right]:
                # 转折点在右边
                if nums[left] <= target <= nums[mid]:
                    return half(left, mid - 1)
                else:
                    return half(mid + 1, right)
            else:
                x = half(left, mid - 1)
                y = half(mid + 1, right)
                return x or y

        return half(0, len(nums) - 1)
